We consider a Carrier Sense Multiple Access (CSMA) based scheduling algorithmfor a single-hop wireless network under a realisticSignal-to-interference-plus-noise ratio (SINR) model for the interference. Wepropose two local optimization based approximation algorithms to efficientlyestimate certain attempt rate parameters of CSMA called fugacities. It is knownthat adaptive CSMA can achieve throughput optimality by sampling feasibleschedules from a Gibbs distribution, with appropriate fugacities.Unfortunately, obtaining these optimal fugacities is an NP-hard problem.Further, the existing adaptive CSMA algorithms use a stochastic gradientdescent based method, which usually entails an impractically slow (exponentialin the size of the network) convergence to the optimal fugacities. To addressthis issue, we first propose an algorithm to estimate the fugacities, that cansupport a given set of desired service rates. The convergence rate and thecomplexity of this algorithm are independent of the network size, and dependonly on the neighborhood size of a link. Further, we show that the proposedalgorithm corresponds exactly to performing the well-known Bethe approximationto the underlying Gibbs distribution. Then, we propose another local algorithmto estimate the optimal fugacities under a utility maximization framework, andcharacterize its accuracy. Numerical results indicate that the proposed methodshave a good degree of accuracy, and achieve extremely fast convergence tonear-optimal fugacities, and often outperform the convergence rate of thestochastic gradient descent by a few orders of magnitude.
展开▼
